/*
 * @lc app=leetcode.cn id=416 lang=javascript
 *
 * [416] 分割等和子集
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {boolean}
 */
var canPartition = function (nums) {
  let size = nums.length;
  // 计算总和
  let sum = nums.reduce((acc, cur) => acc + cur);
  // 奇数不能平分，肯定没有等和子集
  if ((sum & 1) === 1) return false;

  sum /= 2;

  // 前i个数字和是否等于j
  const dp = new Array(size + 1).fill(0).map(() => new Array(sum + 1).fill(false));

  for (let i = 0; i <= size; i++) {
    // base case
    // 空间为0的话，肯定是满的了
    dp[i][0] = true;
  }

  for (let i = 1; i <= size; i++) {
    for (let j = 1; j <= sum; j++) {
      if (j - nums[i - 1] >= 0) {
        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[size][sum];
};
// @lc code=end
